/*
 * @lc app=leetcode id=451 lang=cpp
 *
 * [451] Sort Characters By Frequency
 */

// @lc code=start
class Solution {
public:
    string frequencySort(string s) {
        int w[128] = {0};
        for (auto c : s) {
            w[c]++;
        }
        auto cmp = [](const std::pair<char, int> &lhs, const std::pair<char, int> &rhs) {
            return lhs.second < rhs.second;
        };
         std::priority_queue<std::pair<char, int>, std::vector<std::pair<char, int>>, decltype(cmp)> pq(cmp); 
        for (int i = 0; i < 128; ++i) {
            if (w[i] > 0) {
                std::pair<char, int> value(i, w[i]);
                pq.push(value);
            }
        }
        std::string ans;
        while(!pq.empty()) {
            std::string str(pq.top().second, pq.top().first);
            ans += str;
            pq.pop();
        }
        return ans;

    }
};
// @lc code=end

